package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/12/16 0016.
 */

/**
 * Important
 */
public class Permutations_II {
    /*private List<List<Integer>> rst = new LinkedList<List<Integer>>();
    private LinkedList<Integer> tmp = new LinkedList<Integer>();
    private void permute(int[] num,int start){
        if(start==num.length){
            List<Integer> r = new LinkedList<Integer>(tmp);
            if(!rst.contains(r))
                rst.add(r);
        }
        for(int i=start;i<num.length;i++){
            if(i!=start && num[i]==num[start])
                continue;
            int t = num[i];
            num[i] = num[start];
            num[start] = t;
            tmp.add(t);
            permute(num,start+1);
            tmp.removeLast();
            t = num[i];
            num[i] = num[start];
            num[start] = t;

            int I = num[i];
            for(;i<num.length && num[i]==I;i++);
            i--;
        }
    }
    public List<List<Integer>> permuteUnique(int[] num) {
        if(num!=null && num.length>0){
            Arrays.sort(num);
            permute(num, 0);
        }
        return rst;
    }*/
        public List<List<Integer>> permuteUnique(int[] num) {
            Arrays.sort(num);
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            List<Integer> current = new ArrayList<Integer>();
            boolean[] visited = new boolean[num.length];
            permute(result, current, num, visited);
            return result;
        }

        private void permute(List<List<Integer>> result, List<Integer> current, int[] num, boolean[] visited) {
            if (current.size() == num.length) {
                result.add(new ArrayList<Integer>(current));
                return;
            }
            for (int i=0; i<visited.length; i++) {
                if (!visited[i]) {
                    if (i > 0 && num[i] == num[i-1] && visited[i-1]) {
                        return;
                    }
                    visited[i] = true;
                    current.add(num[i]);
                    permute(result, current, num, visited);
                    current.remove(current.size()-1);
                    visited[i] = false;
                }
            }
        }
    public static void main(String[] args){

        Permutations_II permutations_ii = new Permutations_II();
        int[] num = {-1,-1,0,0,1,1,2};
        List<List<Integer>> rst = permutations_ii.permuteUnique(num);
        for(List<Integer> list:rst){
            System.out.println(list);
        }
    }
}
